// https://leetcode.cn/problems/longest-increasing-subsequence/

// 算法思路总结：
// 1. 记忆化搜索求解最长递增子序列长度
// 2. 从每个位置出发，递归查找后续更大的元素
// 3. memo[pos]记录从pos开始的最长递增子序列长度
// 4. 遍历所有起始位置，取最大值作为结果
// 5. 时间复杂度：O(n²)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <cstring>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    int m;
    int memo[2501];

    int lengthOfLIS(vector<int>& nums) 
    {
        m = nums.size();
        memset(memo, -1, sizeof(memo));

        int ret = 0;
        for (int i = 0 ; i < m ; i++)
        {
            ret = max(ret, dfs(i, nums));
        }

        return ret;
    }

    int dfs(int pos, vector<int>& nums)
    {
        if (memo[pos] != -1)
            return memo[pos];

        int ret = 1;
        for (int i = pos + 1; i < m ; i++)
        {
            if (nums[i] > nums[pos])
                ret = max(ret, dfs(i, nums) + 1);
        }

        return memo[pos] = ret;
    }
};

int main()
{
    vector<int> v1 = {10,9,2,5,3,7,101,18}, v2 = {0,1,0,3,2,3};
    Solution sol;

    cout << sol.lengthOfLIS(v1) << endl;
    cout << sol.lengthOfLIS(v2) << endl;

    return 0;
}